import collections
from typing import List


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def _is_valid(x, y):
            return 0 <= x < m and 0 <= y < n

        def _get_neighbors(x1, y1):
            return [(x2, y2) for (x2, y2) in [(x1 - 1, y1), (x1 + 1, y1), (x1, y1 - 1), (x1, y1 + 1)]
                    if _is_valid(x2, y2)]

        island = 0
        map_dict = {}
        for i1 in range(m):
            for j1 in range(n):
                if grid[i1][j1] == 1 and (i1, j1) not in map_dict:
                    visited = {(i1, j1)}
                    queue = collections.deque([(i1, j1)])
                    while queue:
                        i2, j2 = queue.popleft()
                        for (i3, j3) in _get_neighbors(i2, j2):
                            if grid[i3][j3] == 1 and (i3, j3) not in visited:
                                queue.append((i3, j3))
                                visited.add((i3, j3))
                    size = len(visited)
                    for (i2, j2) in visited:
                        map_dict[(i2, j2)] = (island, size)
                    island += 1

        ans = 0
        for i1 in range(m):
            for j1 in range(n):
                if grid[i1][j1] == 0:
                    island = set()
                    for (i2, j2) in _get_neighbors(i1, j1):
                        if (i2, j2) in map_dict:
                            island.add(map_dict[(i2, j2)])
                    island = sum([size for i, size in island])
                    ans = max(ans, 1 + island)

        return ans if ans > 0 else m * n


if __name__ == "__main__":
    # 3
    print(Solution().largestIsland([[1, 0],
                                    [0, 0]]))

    # 4
    print(Solution().largestIsland([[1, 1],
                                    [1, 0]]))

    # 4
    print(Solution().largestIsland([[1, 1],
                                    [1, 1]]))
